#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

void list_tail_insert(LinkList &L)
{
    L= (LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    ElemType x;
    scanf("%d",&x);
    LNode *s,*r=L;  //s是用来指向申请的新节点,r始终指向链表尾部
    while (x!=9999)
    {
        s=(LinkList)malloc(sizeof(LNode));
        s->data=x;
        r->next=s; //尾指针的next指向新结点
        r=s; //r要指向新的尾部
        scanf("%d",&x);
    }
    r->next=NULL; //结束时让尾指针的next指向NULL
}
void printf_list(LinkList L)
{
    L=L->next;
    while (L!=NULL)
    {
        printf("%3d",L->data);
        L=L->next;
    }
    printf("\n");
}
//找到中间结点，并设置好L2链表
void find_middle(LinkList L,LinkList &L2)
{
    L2=(LinkList)malloc(sizeof(LNode)); //第二条链表的头结点
    LinkList pcur,ppre;   //双指针遍历是考研常考的
    pcur=ppre=L->next;
    while(pcur)           //pcur每次走两步，ppre每次走一步
    {
        //虽然pcur每次走两步，但是每步都要检查一下pcur是否为NULL,为NULL就要结束
        pcur=pcur->next;  //pcur的第一步
        if(NULL==pcur)    //为了防止pcur为NULL
        {
            break;
        }
        pcur=pcur->next;  //pcur的第二步
        if(NULL==pcur)    //为了使偶数个结点时，ppre依然指向a1,a2,...a6中的a3结点
        {
            break;
        }
        ppre=ppre->next;  //ppre每次走一步，不用检查是否为null,因为前面pcur已经检查过了
    }
    L2->next=ppre->next;  //由L2结点指向另外一半链表,ppre就是找到的中间结点
    ppre->next=NULL;      //前一半链表的最后一个结点的next要为NULL
}
void reverse(LinkList L2)
{
    LinkList r,s,t;
    r=L2->next;
    if(r==NULL)  //若L2链表为空，没有元素直接返回
    {
        return;
    }
    s=r->next;
    if(s==NULL)  //若只有一个结点
    {
        return;
    }
    t=s->next;
    while (t)
    {
        s->next=r; //原地逆置
        r=s;       //以下三句是，三个指针同时向后移动一步
        s=t;
        t=t->next;
    }
    s->next=r;  //t为空时最后一个结点还没有逆置，需要在循环外逆置
    L2->next->next=NULL; //逆置后原来的第一个结点要设为NULL
    L2->next=s; //逆置后的链表头结点是s, L2链表指向第一个位置
}
void merge(LinkList L,LinkList L2)
{
    LinkList pcur,p,q;
    pcur=L->next; //pcur始终指向合并后的链表的链表尾
    p=pcur->next; //p是用来遍历L链表的
    q=L2->next;   //q指向L2第一个结点,q是用来遍历L2链表的
    while (p!=NULL&&q!=NULL)
    {
        pcur->next=q;
        q=q->next;       //指向L2下一个结点
        pcur=pcur->next; //尾指针向后移动一个
        pcur->next=p;
        p=p->next;       //指向L下一个结点
        pcur=pcur->next; //尾指针向后移动一个
    }
    // 任何一个链表都可能剩余一个结点，放进来即可
    if(p!=NULL)    //判断谁的链表剩下一个元素
    {
        pcur->next=p;
    }
    if(q!=NULL)
    {
        pcur->next=q;
    }
}

int main() {
    LinkList L;  //L是链表头指针，是结构体指针类型1 2 3 4 5 6 7 8 9 10 9999
    list_tail_insert(L); //尾插法来新建链表
    printf_list(L);
    printf("--------------------\n");

    // 寻找中间结点，并返回第二条链表
    LinkList L2=NULL;
    find_middle(L,L2);
    printf_list(L);
    printf_list(L2);
    printf("--------------------\n");

    // L2的原地逆转
    reverse(L2);
    printf_list(L2);
    printf("--------------------\n");

    // 合并L和L2
    merge(L,L2);
    free(L2);
    printf_list(L);
    printf("--------------------\n");
    return 0;
}
